#include "evaluate.h"

extern int gridUnit;
extern int x_gridNum;
extern int y_gridNum;
extern int numBins;
extern ckt this_ckt;
extern double HPWL, penalty, displacement, max_displacement, targUt;
extern string directory;
extern vector<double> util_array;

void bin_manipulation_check(ckt & ptrckt)
{
	ptrckt.tinyRows.clear();
	tinyRow_setup(ptrckt);

	//Perform manipulation
	for(int i = 0; i < numBins; i++)
	{
		bin_optimization_check(ptrckt, i);
	}
}

void bin_optimization_check(ckt & ptrckt, int binID)
{
	int row;
	vector< pair<int,int> > node_list;
	// Preparation, add candidate Node_IDs into list
	for(row = 0; row < 9; row++)
	{
		tinyRow & this_row = ptrckt.tinyRows[index_translate(binID, row)];
		if(this_row.isValid && this_row.NodeID.size() != 0)
		{
			for(int i = 0; i < this_row.NodeID.size(); i++)
			{
				if(!ptrckt.nodes[this_row.NodeID[i]].isFixed)
				{
					node_list.push_back(make_pair(row, this_row.NodeID[i]));
				}
			}
			//row_swap_optimization_check(ptrckt, this_row);
		}
	}
	if(node_list.size() == 0)
		return;

	// Perform manipulation to optimize wirelength
	vector< pair<int,int> >::iterator it;
	for(it = node_list.begin(); it != node_list.end(); ++it)
	{
		node & this_node = ptrckt.nodes[it->second];
		pair<int,int> pr = find_best_row_check(ptrckt, it->first, binID, this_node);
		tinyRow & src_row = ptrckt.tinyRows[index_translate(binID, it->first)];

		if(pr.first != it->first) // Need to be moved
		{
			tinyRow & dest_row = ptrckt.tinyRows[index_translate(binID, pr.first)];
			if(insert2site_check(ptrckt, this_node, dest_row, pr.second))
				erase_src_node(ptrckt, src_row, this_node.ID);
		}
	}
}



bool row_swap_optimization_check(ckt & ptrckt, tinyRow & this_row)
{
	assert(this_row.isValid);
	sort(this_row.NodeID.begin(), this_row.NodeID.end(), compareNodeID());
	if(this_row.NodeID.size() == 0 || this_row.isValid == false)
		return false;
	else if(this_row.NodeID.size() == 1)
	{
		node & this_node = ptrckt.nodes[this_row.NodeID[0]];
		if(this_node.isFixed)
			return false;
		else
		{
			// Move node in current tinyrow
			move_node_in_row_check(ptrckt, this_node, this_row.lx, this_row.rx - this_node.width, 5);
			// Updating the boundary of current tinyrow
			fixRow(ptrckt, this_row);
			return true;
		}
	}
	else if(this_row.NodeID.size() == 2)
	{
		if(!ptrckt.nodes[this_row.NodeID[0]].isFixed && !ptrckt.nodes[this_row.NodeID[1]].isFixed)
		{
			bi_swap_check(ptrckt, this_row, 0);
			fixRow(ptrckt, this_row);
		}
		return true;
	}
	else
	{
		for(int i = 0; i < this_row.NodeID.size() - 2; i++)
		{
			node & node1 = ptrckt.nodes[this_row.NodeID[i]];
			node & node2 = ptrckt.nodes[this_row.NodeID[i + 1]];
			node & node3 = ptrckt.nodes[this_row.NodeID[i + 2]];
			if(!node1.isFixed && !node2.isFixed && !node3.isFixed)
			{
				tri_swap_check(ptrckt, this_row, i);
			}
			else if(node1.isFixed && !node2.isFixed && !node3.isFixed)
			{
				bi_swap_check(ptrckt, this_row, i + 1);
			}
		}
		return true;
	}
}
int bi_swap_check(ckt & ptrckt, tinyRow & this_row, int index)
{
	node & node1 = ptrckt.nodes[this_row.NodeID[index]];
	node & node2 = ptrckt.nodes[this_row.NodeID[index + 1]];
	int lx = node1.x_coord;
	int rx = node2.x_coord + node2.width;

	// CHECK
	if(cell_displacement(lx, this_row.y, node2) >= max_displacement)
		return 0;
	if(cell_displacement(rx - node1.width, this_row.y, node1) >= max_displacement)
		return 0;

	set<int> related_nets;
	vector<pin>::iterator it;
	for(it = node1.pins.begin(); it != node1.pins.end(); ++it)
		related_nets.insert(it->pin2net);
	for(it = node2.pins.begin(); it != node2.pins.end(); ++it)
		related_nets.insert(it->pin2net);

	// Evaluate each possibility
	// Case 1:
	int best_order = 1;
	int local_HPWL = calculate_local_HPWL(ptrckt, related_nets);
	int best_HPWL = local_HPWL;
	
	// Case 2: 2.1.
	node2.x_coord = lx;
	node1.x_coord = rx - node1.width;
	local_HPWL = calculate_local_HPWL(ptrckt, related_nets);
	if(local_HPWL < best_HPWL)
	{
		best_HPWL = local_HPWL;
		best_order = 2;
	}

	switch(best_order)
	{
		case 1:
			node1.x_coord = lx;
			node2.x_coord = rx - node2.width;
			break;
		case 2:
			this_row.NodeID[index] = node2.ID;
			this_row.NodeID[index + 1] = node1.ID;
			break;
	}
	fixNet(ptrckt, node1);
	fixNet(ptrckt, node2);
	return best_order;
}

int tri_swap_check(ckt & ptrckt, tinyRow & this_row, int index)
{
	// Reference of the nodes
	node & node1 = ptrckt.nodes[this_row.NodeID[index]];
	node & node2 = ptrckt.nodes[this_row.NodeID[index + 1]];
	node & node3 = ptrckt.nodes[this_row.NodeID[index + 2]];
	// Standard position of the nodes
	int lx = node1.x_coord;
	int rx = node3.x_coord + node3.width;
	int mutual_distance = (rx - lx - node1.width - node2.width - node3.width) / 2;
	// Add related nets to a set
	set<int> related_nets;
	vector<pin>::iterator it;
	for(it = node1.pins.begin(); it != node1.pins.end(); ++it)
		related_nets.insert(it->pin2net);
	for(it = node2.pins.begin(); it != node2.pins.end(); ++it)
		related_nets.insert(it->pin2net);
	for(it = node3.pins.begin(); it != node3.pins.end(); ++it)
		related_nets.insert(it->pin2net);
	// Evaluate each possibility
	int best_order;
	int best_HPWL;
	int local_HPWL;
	
	// Case 0:
	int x1 = node1.x_coord;
	int x2 = node2.x_coord;
	int x3 = node3.x_coord;
	local_HPWL = calculate_local_HPWL(ptrckt, related_nets);
	best_order = 0;
	best_HPWL = local_HPWL;

	// Case 1: 1.2.3.
	node1.x_coord = lx;
	node2.x_coord = lx + node1.width + mutual_distance;
	node3.x_coord = rx - node3.width;
	local_HPWL = calculate_local_HPWL(ptrckt, related_nets);
	best_order = 1;
	best_HPWL = local_HPWL;
	if(local_HPWL < best_HPWL)
	{
		if(cell_displacement(node1.x_coord, node1.y_coord, node1) < max_displacement
		&& cell_displacement(node2.x_coord, node2.y_coord, node2) < max_displacement
		&& cell_displacement(node3.x_coord, node3.y_coord, node3) < max_displacement)
		{
			best_HPWL = local_HPWL;
			best_order = 1;
		}
	}
	
	// Case 2: 1.3.2.
	node1.x_coord = lx;
	node3.x_coord = lx + node1.width + mutual_distance;
	node2.x_coord = rx - node2.width;
	local_HPWL = calculate_local_HPWL(ptrckt, related_nets);
	if(local_HPWL < best_HPWL)
	{
		if(cell_displacement(node1.x_coord, node1.y_coord, node1) < max_displacement
		&& cell_displacement(node2.x_coord, node2.y_coord, node2) < max_displacement
		&& cell_displacement(node3.x_coord, node3.y_coord, node3) < max_displacement)
		{
			best_HPWL = local_HPWL;
			best_order = 2;
		}
	}
	
	// Case 3: 2.1.3.
	node2.x_coord = lx;
	node1.x_coord = lx + node2.width + mutual_distance;
	node3.x_coord = rx - node3.width;
	local_HPWL = calculate_local_HPWL(ptrckt, related_nets);
	if(local_HPWL < best_HPWL)
	{
		if(cell_displacement(node1.x_coord, node1.y_coord, node1) < max_displacement
		&& cell_displacement(node2.x_coord, node2.y_coord, node2) < max_displacement
		&& cell_displacement(node3.x_coord, node3.y_coord, node3) < max_displacement)
		{
			best_HPWL = local_HPWL;
			best_order = 3;
		}
	}
	
	// Case 4: 2.3.1.
	node2.x_coord = lx;
	node3.x_coord = lx + node2.width + mutual_distance;
	node1.x_coord = rx - node1.width;
	local_HPWL = calculate_local_HPWL(ptrckt, related_nets);
	if(local_HPWL < best_HPWL)
	{
		if(cell_displacement(node1.x_coord, node1.y_coord, node1) < max_displacement
		&& cell_displacement(node2.x_coord, node2.y_coord, node2) < max_displacement
		&& cell_displacement(node3.x_coord, node3.y_coord, node3) < max_displacement)
		{
			best_HPWL = local_HPWL;
			best_order = 4;
		}
	}
	
	// Case 5: 3.1.2.
	node3.x_coord = lx;
	node1.x_coord = lx + node3.width + mutual_distance;
	node2.x_coord = rx - node2.width;
	local_HPWL = calculate_local_HPWL(ptrckt, related_nets);
	if(local_HPWL < best_HPWL)
	{
		if(cell_displacement(node1.x_coord, node1.y_coord, node1) < max_displacement
		&& cell_displacement(node2.x_coord, node2.y_coord, node2) < max_displacement
		&& cell_displacement(node3.x_coord, node3.y_coord, node3) < max_displacement)
		{
			best_HPWL = local_HPWL;
			best_order = 5;
		}
	}
	
	// Case 6: 3.2.1.
	node3.x_coord = lx;
	node2.x_coord = lx + node3.width + mutual_distance;
	node1.x_coord = rx - node1.width;
	local_HPWL = calculate_local_HPWL(ptrckt, related_nets);
	if(local_HPWL < best_HPWL)
	{
		if(cell_displacement(node1.x_coord, node1.y_coord, node1) < max_displacement
		&& cell_displacement(node2.x_coord, node2.y_coord, node2) < max_displacement
		&& cell_displacement(node3.x_coord, node3.y_coord, node3) < max_displacement)
		{
			best_HPWL = local_HPWL;
			best_order = 6;
		}
	}

	switch(best_order)
	{
		case 0:
			node1.x_coord = x1;
			node2.x_coord = x2;
			node3.x_coord = x3;
			break;
		case 1: // 1 2 3
			node1.x_coord = lx;
			node2.x_coord = lx + node1.width + mutual_distance;
			node3.x_coord = rx - node3.width;
			break;
		case 2: // 1 3 2
			node1.x_coord = lx;
			node3.x_coord = lx + node1.width + mutual_distance;
			node2.x_coord = rx - node2.width;
			this_row.NodeID[index + 1] = node3.ID;
			this_row.NodeID[index + 2] = node2.ID;
			break;
		case 3: // 2 1 3
			node2.x_coord = lx;
			node1.x_coord = lx + node2.width + mutual_distance;
			node3.x_coord = rx - node3.width;
			this_row.NodeID[index] 	   = node2.ID;
			this_row.NodeID[index + 1] = node1.ID;
			break;
		case 4: // 2 3 1
			node2.x_coord = lx;
			node3.x_coord = lx + node2.width + mutual_distance;
			node1.x_coord = rx - node1.width;
			this_row.NodeID[index] 	   = node2.ID;
			this_row.NodeID[index + 1] = node3.ID;
			this_row.NodeID[index + 2] = node1.ID;
			break;
		case 5: // 3 1 2
			node3.x_coord = lx;
			node1.x_coord = lx + node3.width + mutual_distance;
			node2.x_coord = rx - node2.width;
			this_row.NodeID[index] 	   = node3.ID;
			this_row.NodeID[index + 1] = node1.ID;
			this_row.NodeID[index + 2] = node2.ID;
			break;
		case 6: // 3 2 1
			this_row.NodeID[index] 	   = node3.ID;
			this_row.NodeID[index + 2] = node1.ID;
			break;
	}
	fixNet(ptrckt, node1);
	fixNet(ptrckt, node2);
	fixNet(ptrckt, node3);
	return best_order;
}

bool move_node_in_row_check(ckt & ptrckt, node & this_node, int left_bound, int right_bound, int step)
{
	int best_move = 0;
	int best_reduction = 0;
	for(int move = left_bound - this_node.x_coord; move <= right_bound - this_node.x_coord; move += step)
	{
		if(cell_displacement(this_node.x_coord + move, this_node.y_coord, this_node) >= max_displacement * 0.95)
			continue;
		if(move == 0)
			continue;
		int reduction = delta_HPWL(ptrckt, this_node.ID, move, 0);
		if(reduction < best_reduction)
		{
			best_move = move;
			best_reduction = reduction;
		}
	}
	if(best_reduction < 0)
	{
		this_node.x_coord += best_move;
		fixNet(ptrckt, this_node);
		return true;
	}
	return false;
}


// bool insert2site_check(ckt & ptrckt, node & this_node, tinyRow & dest_row, int x)
// {	
// 	assert(!this_node.isFixed);
// 	assert(dest_row.isValid);
// 	assert(x >= 0);
// 	assert(x <= dest_row.rx);

// 	if(cell_displacement(dest_row.lx + x, dest_row.y, this_node) >= max_displacement * 0.95)
// 		return false;

// 	query answer;
// 	if(space_query(ptrckt, this_node, dest_row, x, answer)) // Dummy Insert
// 	{
// 		if(answer.space >= this_node.width) // Can insert directly
// 		{
// 			if(answer.cellID_left == -1) // No cell on the left of x
// 			{
// 				this_node.x_coord = dest_row.lx;
// 				this_node.y_coord = dest_row.y;
// 			}
// 			else // At least one cell on the left of x
// 			{
// 				this_node.x_coord = ptrckt.nodes[answer.cellID_left].x_coord + ptrckt.nodes[answer.cellID_left].width;
// 				this_node.y_coord = dest_row.y;
// 				assert(this_node.x_coord >= dest_row.lx);
// 			}

// 			// Can be more efficient
// 			dest_row.NodeID.push_back(this_node.ID);
// 			sort(dest_row.NodeID.begin(), dest_row.NodeID.end(), compareNodeID());
// 			fixNet(ptrckt, this_node);

// 			move_node_in_row_check(ptrckt, this_node, this_node.x_coord, this_node.x_coord + answer.space - this_node.width);
// 			return true;
// 		}
// 		else if(answer.available_space >= this_node.width) // Need to move adjacent cells
// 		{
// 			if(answer.space_left == -1) // right space must exist
// 			{
// 				assert(answer.space_right != -1);
// 				assert(answer.cellID_right != -1);
// 				node & right = ptrckt.nodes[answer.cellID_right];
				
				
// 				right.x_coord += answer.space_right;
// 				assert(right.x_coord + right.width <= dest_row.rx);
// 				fixNet(ptrckt, right);

// 				if(answer.cellID_left == -1)
// 				{
// 					this_node.x_coord = dest_row.lx;
// 					this_node.y_coord = dest_row.y;
// 					assert(ptrckt.nodes[dest_row.NodeID[0]].x_coord >= dest_row.lx + this_node.width);
// 					assert(dest_row.lx >= dest_row.l_end);
// 				}
// 				else
// 				{
// 					assert(ptrckt.nodes[answer.cellID_left].isFixed);
// 					this_node.x_coord = ptrckt.nodes[answer.cellID_left].x_coord + ptrckt.nodes[answer.cellID_left].width;
// 					this_node.y_coord = dest_row.y;
// 				}
// 				fixNet(ptrckt, this_node);
// 				dest_row.NodeID.push_back(this_node.ID);
// 				sort(dest_row.NodeID.begin(), dest_row.NodeID.end(), compareNodeID());

// 				move_node_in_row_check(ptrckt, this_node, this_node.x_coord, right.x_coord - this_node.width, 1);
// 				move_node_in_row_check(ptrckt, right, this_node.x_coord + this_node.width, right.x_coord, 1);

// 				return true;
// 			}
// 			else if(answer.space_right == -1) // left space must exist
// 			{
// 				node & left = ptrckt.nodes[answer.cellID_left];
// 				assert(!left.isFixed);
// 				assert(answer.space + answer.space_left >= this_node.width);

// 				left.x_coord -= answer.space_left;
// 				assert(left.x_coord >= dest_row.lx);
// 				fixNet(ptrckt, left);

// 				this_node.x_coord = left.x_coord + left.width;
// 				this_node.y_coord = dest_row.y;
// 				fixNet(ptrckt, this_node);
// 				dest_row.NodeID.push_back(this_node.ID);
// 				sort(dest_row.NodeID.begin(), dest_row.NodeID.end(), compareNodeID());

// 				if(answer.cellID_right != -1) // right cell is fixed
// 				{
// 					move_node_in_row_check(ptrckt, this_node, left.x_coord + left.width,
// 						ptrckt.nodes[answer.cellID_right].x_coord - this_node.width, 1);
// 					move_node_in_row_check(ptrckt, left, left.x_coord, this_node.x_coord - left.width, 1);
// 				}
// 				else // no cells on the right
// 				{
// 					move_node_in_row_check(ptrckt, this_node, left.x_coord + left.width,
// 						dest_row.rx - this_node.width, 1);
// 					move_node_in_row_check(ptrckt, left, left.x_coord, this_node.x_coord - left.width, 1);
// 				}

// 				return true;
// 			}
// 			else // both left and right space exist and movable
// 			{
// 				assert(answer.cellID_left >= 0);
// 				assert(answer.cellID_right >= 0);
// 				node & left = ptrckt.nodes[answer.cellID_left];
// 				node & right = ptrckt.nodes[answer.cellID_right];

// 				left.x_coord -= answer.space_left;
// 				assert(left.x_coord >= dest_row.lx);
// 				fixNet(ptrckt, left);

// 				right.x_coord += answer.space_right;
// 				assert(right.x_coord + right.width <= dest_row.rx);
// 				fixNet(ptrckt, right);

// 				this_node.x_coord = left.x_coord + left.width;
// 				this_node.y_coord = dest_row.y;
// 				assert(this_node.x_coord + this_node.width <= right.x_coord);
// 				fixNet(ptrckt, this_node);
// 				dest_row.NodeID.push_back(this_node.ID);
// 				sort(dest_row.NodeID.begin(), dest_row.NodeID.end(), compareNodeID());

// 				move_node_in_row_check(ptrckt, this_node, left.x_coord + left.width, right.x_coord - this_node.width, 1);
// 				move_node_in_row_check(ptrckt, left, left.x_coord, this_node.x_coord - left.width, 1);
// 				move_node_in_row_check(ptrckt, right, this_node.x_coord + this_node.width, right.x_coord, 1);

// 				return true;	
// 			}
// 		}	
// 	}
// 	return false;
// }

pair<int,int> find_best_row_check(ckt & ptrckt, int src_row, int binID, node & this_node)
{
	assert(!this_node.isFixed);
	int best_row = src_row;
	int best_reduction = -9;
	int best_x = -1;
	int row;
	int x = this_node.x_coord;
	int y = this_node.y_coord;
	query answer;

	for(row = 0; row < 9; row++)
	{
		if(row == src_row)
		{
			// Could be modified
			// First delete, then pushed back?
			// If not, put it back to the original place?
			continue;
		}
		tinyRow & dest_row = ptrckt.tinyRows[index_translate(binID, row)];
		if(!dest_row.isValid)
			continue;

		if(cell_displacement(dest_row.lx, dest_row.y, this_node) < max_displacement * 0.9)
		{
			if(space_query(ptrckt, this_node, dest_row, 0, answer))
			{
				if(answer.available_space >= this_node.width)
				{
					int reduction = delta_HPWL(ptrckt, this_node.ID, dest_row.lx - x, dest_row.y - y);
					if(answer.space < this_node.width)
						reduction += this_node.width - answer.space;
					if(reduction < best_reduction)
					{
						best_reduction = reduction;
						best_x = 0;
						best_row = row;
					}
				}		
			}
		}

		for(int i = 0; i < dest_row.NodeID.size(); i++)
		{
			int current_x = ptrckt.nodes[dest_row.NodeID[i]].x_coord + ptrckt.nodes[dest_row.NodeID[i]].width - dest_row.lx;
			
			if(cell_displacement(dest_row.lx, dest_row.y, this_node) < max_displacement * 0.9)
			{
				if(space_query(ptrckt, this_node, dest_row, current_x, answer))
				{	
					if(answer.available_space >= this_node.width)
					{
						int reduction = delta_HPWL(ptrckt, this_node.ID, dest_row.lx + current_x - x, dest_row.y - y);
						if(answer.space < this_node.width)
							reduction += this_node.width - answer.space;
						if(reduction < best_reduction)
						{
							best_reduction = reduction;
							best_x = current_x;
							best_row = row;
						}
					}	
				}
			}
		}
	}
	return make_pair(best_row, best_x);
}

void fix_displacement(ckt & ptrckt) // Very Naive
{
	for(unsigned i = 0; i < ptrckt.nodes.size(); i++)
	{
		node & this_node = ptrckt.nodes[i];

		if(this_node.isFixed)
			continue;

		int disp = abs(this_node.x_coord - this_node.initial_x) + abs(this_node.y_coord - this_node.initial_y);


		if(disp > max_displacement)
		{
			cout << disp << endl;
			cout << "Width " << this_node.width << endl;  
			int x = this_node.x_coord;
			int y = this_node.y_coord;
			int src_rowID = xy2tinyRowID(ptrckt, x, y);
			tinyRow & src_row = ptrckt.tinyRows[src_rowID];
			sort(src_row.NodeID.begin(), src_row.NodeID.end(), compareNodeID());

			int index; // The index of the node to move
			for(index = 0; index < src_row.NodeID.size(); index++)
			{
				node & current_node = ptrckt.nodes[src_row.NodeID[index]];
				if(this_node.ID == current_node.ID)
					break;
			}
			
			if(src_row.lx > this_node.initial_x) // Should move left
			{
				/* If '>', there is no need to do the following manipulations */
				if(cell_displacement(src_row.lx, this_node.y_coord, this_node) <= max_displacement)
				{
					// Try to find a place in the tinyRow to insert current node
					int i = 0;
					int previous_node_rx = src_row.lx;
					int place2insert = -1;
					for(i = 0; i < src_row.NodeID.size(); i++)
					{
						node & current_node = ptrckt.nodes[src_row.NodeID[i]];
						if(current_node.ID == this_node.ID)
						{
							if(cell_displacement(previous_node_rx, this_node.y_coord, this_node) <= max_displacement)
							{
								place2insert = previous_node_rx;
							}
							break;
						}
						else
						{
							if(cell_displacement(previous_node_rx, this_node.y_coord, this_node) <= max_displacement)
							{
								int space = current_node.x_coord - previous_node_rx;
								if(space >= this_node.width)
									place2insert = previous_node_rx;
							}
							previous_node_rx = current_node.x_coord + current_node.width;
						}
					}

					if(place2insert != -1)
					{
						this_node.x_coord = place2insert;
						fixNet(ptrckt, this_node);
						continue;
					}

					// If problem cannot be solved by simple movement, try changing the order of cells
					// int target_x = this_node.x_coord - (disp - max_displacement);
					// i = index - 1;
					// while(i >= 0)
					// {
					// 	node & current_node = ptrckt.nodes[src_row.NodeID[i]];
					// 	if(current_node.isFixed)
					// 	{
					// 		i = index;
					// 		break;
					// 	}
					// 	if(current_node.x_coord + current_node.width <= target_x)
					// 	{
					// 		target_x = current_node.x_coord + current_node.width;
					// 		break;
					// 	}
					// 	i--;

					// }
					// if(i != index)
					// {
					// 	int movement = target_x + this_node.width - ptrckt.nodes[src_row.NodeID[i + 1]].x_coord;
					// 	for(int j = i; j < index; j++)
					// 	{
					// 		ptrckt.nodes[src_row.NodeID[i]].x_coord += movement;
					// 	}
					// 	sort(src_row.NodeID.begin(), src_row.NodeID.end(), compareNodeID());
					// 	cout << "Stage 2" << endl;
					// 	continue;
					// }

					// If problem still cannot be solved...



				}
			}
			else if(src_row.rx - this_node.width < this_node.initial_x) // Should move right
			{
				// If '>', there is no need to do the following manipulations
				if(cell_displacement(src_row.rx - this_node.x_coord, this_node.y_coord, this_node) <= max_displacement)
				{
					/* Try to find a place in the tinyRow to insert current node */
					int i;
					int previous_node_rx = this_node.x_coord;
					int place2insert = -1;
					for(i = index + 1; i < src_row.NodeID.size(); i++)
					{
						node & current_node = ptrckt.nodes[src_row.NodeID[i]];
						if(cell_displacement(current_node.x_coord - this_node.width, this_node.y_coord, this_node) <= max_displacement)
						{
							int space = current_node.x_coord - previous_node_rx;
							if(space >= this_node.width)
							{
								place2insert = current_node.x_coord - this_node.width;
								break;
							}
						}
						previous_node_rx = current_node.x_coord + current_node.width;
					}


					/* If we could not find one usable blank in the above loop */
					if(i == src_row.NodeID.size()) 
					{
						if(cell_displacement(src_row.rx - this_node.width, this_node.y_coord, this_node) <= max_displacement)
						{
							int space = src_row.rx - previous_node_rx;
							if(space >= this_node.width)
							{
								place2insert = src_row.rx - this_node.width;
							}
						}
					}

					if(place2insert != -1)
					{
						this_node.x_coord = place2insert;
						fixNet(ptrckt, this_node);
						continue;
					}

					// If problem cannot be solved by simple movement, try changing the order of cells
					// int target_x = this_node.x_coord + this_node.width + (disp - max_displacement)
					// i = index + 1;
					// while(i < src_row.NodeID.size())
					// {
					// 	node & current_node = ptrckt.nodes[src_row.NodeID[i]];
					// 	if(current_node.isFixed)
					// 	{
					// 		i = index;
					// 		break;
					// 	}
					// 	if(current_node.x_coord + current_node.width >= target_x)
					// 	{
					// 		target_x = current_node.x_coord + current_node.width;
					// 		break;
					// 	}
					// 	i++;
					// }
					// if(i != index)
					// {
					// 	int movement = target_x + this_node.width - ptrckt.nodes[src_row.NodeID[i + 1]].x_coord;
					// 	for(int j = i; j < index; j++)
					// 	{
					// 		ptrckt.nodes[src_row.NodeID[i]].x_coord += movement;
					// 	}
					// 	sort(src_row.NodeID.begin(), src_row.NodeID.end(), compareNodeID());
					// 	continue;
					// }

				}
			}

			 	
			
		}

	}
}